Branch prediction is one technique used to improve data processor performance. If the operands on which a branch instruction depends are not available, then a dam processor must either predict the outcome of the branch instruction or must stall the branch instruction until the operands are available. If the data processor stalls, or delays executing the branch instruction, then it can not determine what instructions it needs next. Such a delay will significantly impact the performance of the data processor.
Data processors that use branch prediction techniques make a "guess" each time they receive a branch instruction, act on the guess, and then determine if the guess was correct by executing the instruction. Such a data processor guesses whether a branch will ultimately be taken and "jump" to a new instruction address or whether it will "fall through" to the next sequential instruction. Data processors that predict branch instructions gain performance because they can make an accurate guess faster than they can fully execute the branch instruction. These data processors then need only correct wrong guesses.
Branch target address caches ("BTACs") are devices used to make branch predictions. BTACs contain addresses to which the data processor has recently branched. These "branch targets" are indexed by the address of the branch instruction which generated them. The data processor will search the BTAC once it determines the address of any instruction that it should next execute. If the address corresponds to a valid entry in the BTAC, then the data processor assumes that it will take the branch again and will automatically branch to the corresponding cached target address. If the address does not correspond to any valid entry in the BTAC, then the data processor will determine the address of its next instruction by some other method.
A data processor incorporating a BTAC updates its BTAC after it executes each branch instruction and determines a target address. Known data processors then store the address of the branch instruction and its target address in the BTAC. Some data processors only store address-target address pairs of branch instructions that are taken. Those that are not taken are either not stored in the BTAC or are deleted if they are already stored in the BTAC. This methodology minimizes the size of the BTAC since the not-taken or sequential address is easily determined.
A BTAC's storage algorithm can degrade the performance of a data processor incorporating the BTAC if each entry in the BTAC is associated with more than one instruction. A single BTAC entry may be associated with more than one instruction to reduce BTAC look-up time and size. In of these cases, two or more different branch instructions may be associated with the, same BTAC entry depending upon the programmed instruction stream. However, these two different branch instructions may have different target address and may or may not be taken independently of each other.